◀ Prev · Parts · Full · Next ▶

Consider a casino offering fair odds at a roulette table. The roulette table generates a sequence of random numbers. If this sequence is algorithmically random, then there is no lower semi-computable strategy to win, which in turn implies that there is no computable strategy to win. That is, for any gambling algorithm, the long-term log-payoff is zero (neither positive nor negative). Conversely, if this sequence is not algorithmically random, then there is a lower semi-computable strategy to win.

• Chaitin's halting probability Ω is an example of a random sequence.

• Every random sequence is not computable.

• Every random sequence is normal, satisfies the law of large numbers, and satisfies all Turing-computable properties satisfied by an IID stream of uniformly random numbers. (Theorem 14.5.2 cite-ref-0-10-1[10])

• RANDc (the complement of RAND) is a measure 0 subset of the set of all infinite sequences. This is implied by the fact that each constructive null cover covers a measure 0 set, there are only countably many constructive null covers, and a countable union of measure 0 sets has measure 0. This implies that RAND is a measure 1 subset of the set of all infinite sequences.

◀ Prev · Parts · Full · Next ▶